package com.unionfind;

/**
 *
 * QU quick union
 * R ranks
 * @Author: tgy
 * @Date: 2020-10-20 11:22
 */
public class UnionFind_QU_R extends UnionFind_QU {

    private int[] ranks;

    public UnionFind_QU_R(int capacity) {
        super(capacity);

        ranks = new int[parents.length];

        for (int i = 0; i < ranks.length; i++) {

            ranks[i] = 1;
        }
    }


    @Override
    protected void assignParent(int pv1, int pv2) {


        /**
         * 树高低的加在树高高的上面
         */
        if (ranks[pv1] > ranks[pv2]) {

            parents[pv2] = pv1;
        }else if (ranks[pv1] < ranks[pv2]) {

            parents[pv1] = pv2;
        }else {

            /**
             * 树高相等，随便加在哪一个树上面，同时树高+1
             */
            parents[pv2] = pv1;
            ranks[pv1]++;
        }
    }
}
